package leetcode;

public class T37 {

    char[] nums = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};

    public void solveSudoku(char[][] board) {
        boolean circle = circle(board, 0, 0);
        System.out.println(circle);
    }

    public boolean circle(char[][] board, int x, int y) {
        System.out.println(x+" "+y);
        if (x == board[0].length) {
            x = 0;
            y++;
            return circle(board, x, y);
        }

        if (y == board.length) {
            return true;
        }


        if ('.' != board[y][x]) {
            return circle(board, ++x, y);
        }


        for (int t = 0; t < nums.length; t++) {
            if (exist(board, x, y, nums[t])) {
                continue;
            }
            board[y][x] = nums[t];
            if (circle(board, x + 1, y)) {
                return true;
            }
            board[y][x] = '.';
        }

        return false;
    }

    boolean exist(char[][] board, int x, int y, char c) {
        //当前行存在
        for (int i = 0; i < board[y].length; i++) {
            if (c == board[y][i]) {
                return true;
            }
        }

        //当前列存在
        for (int i = 0; i < board.length; i++) {
            if (c == board[i][x]) {
                return true;
            }
        }
        //当前小的九宫格存在
        int xStart = x - x % 3;
        int yStart = y - y % 3;
        for (int i = xStart; i < xStart + 3; i++) {
            for (int j = yStart; j < yStart + 3; j++) {
                if (c == board[j][i]) {
                    return true;
                }
            }
        }
        return false;

    }


    public static void main(String[] args) {
        T37 t37 = new T37();
        char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        t37.solveSudoku(board);
        System.out.println(board);
        for (int j = 0; j < board.length; j++) {
            for (int i = 0; i < board[0].length; i++) {
                System.out.print(board[j][i]);
            }
            System.out.println();
        }
    }
}
